package com.github.yangyishe.p500;

import java.util.ArrayList;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
 * 方案2已解决
 *
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 *
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 *
 *
 *
 * 示例 1:
 *
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 *  示例 2:
 *
 * 输入: s = "abab", p = "ab"
 * 输出: [0,1,2]
 * 解释:
 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 *
 *
 * 提示:
 *
 * 1 <= s.length, p.length <= 3 * 104
 * s 和 p 仅包含小写字母
 */
public class Problem438 {
    public static void main(String[] args) {
        String s="abcabccbbaa";
        String p="aabbcc";

        Problem438 problem438 = new Problem438();
        List<Integer> anagrams = problem438.findAnagrams(s, p);
        System.out.println("anagrams = " + anagrams);

    }

    /**
     * 思路:
     * 暴力破解: 查询每一个初始位置, 对是否符合子串条件进行判定.
     *
     * 优化:
     * 对字符串p进行统计, 统计每个字符的数量.
     * 遍历字符串s, 每遍历一个字符, 则对对应位置的字符count-1.
     * 如果遇到-1的情况, 则重置字符count;
     * 如果每个字符的count都为0后, 则记录初始位置, 并在初始位置的字符count+1.
     *
     * 逻辑再整理：
     * 对于p而言，顺序是没有任何意义的。
     * 关键是当读到某个字符开始，记录读的位置，后续情况，无非以下几种：
     * 1。读到可容纳字符，在容器中记录字符并判断：如果此时容器已满，则记录开始索引，并将继续。（不需要排出字符）
     * 2。读到不可容纳字符，陆续排出字符直到字符可被容纳，或者容器为空为止；
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        //1. 统计每个字符的数量
        char[] charsp = p.toCharArray();
        int[] pcounts=new int[26];
        for(char c:charsp){
            pcounts[c-'a']++;
        }
        int initPositiveCount=0;
        for(int i:pcounts){
            if(i>0){
                initPositiveCount++;
            }
        }
        List<Integer> resultList=new ArrayList<>();

        //2. 克隆出遍历字符集, 并对遍历母字符串
        int[] temp=new int[26];
        System.arraycopy(pcounts,0,temp,0,pcounts.length);
        int positiveCount=initPositiveCount;

        for(int i=0;i<s.length();i++){
            // 共计3种处理情况
            // a) 无关字符, 重置并跳过
            // b) 相关字符, 不可处理(count=0), 首尾相衔, 不处理
            // c) 相关字符, 不可处理(count=0), 首尾不相衔, 重置同时处理当前位
            // d) 相关字符, 可处理
            char c=s.charAt(i);
            // a)
            if(pcounts[c-'a']==0){
                System.arraycopy(pcounts,0,temp,0,pcounts.length);
                positiveCount=initPositiveCount;
                continue;
            }

            if(temp[c-'a']==0){
                // b)
                // 先检查是否是首尾相衔的情况, 是的话优先处理
                int startIndex=i-p.length()+1;
                if(startIndex>=0&&s.charAt(startIndex)==c){
                    continue;
                }
                // c)
                // 再检查是否当前count已经=0, 如果是, 则重置
                // todo 此处不应当重置, 而应当恢复到最小索引上
                System.arraycopy(pcounts,0,temp,0,pcounts.length);
                positiveCount=initPositiveCount;
            }

            temp[c-'a']--;
            if(temp[c-'a']==0){
                positiveCount--;
            }
            //2.1. 如果遇到count=-1的情况, 则重置
            // count=-1的情况:1. 遇到p中不存在的字符;2.遇到p中过多的字符. 如果是后者, 需要先检查第一个字符是否也是这个字符, 如果是, 则直接pass即可

            //2.2. 如果每个字符的count=0, 则记录初始位置, 并在初始位置字符count+=1
            if(positiveCount==0){
                int startIndex=i-p.length()+1;
                resultList.add(startIndex);

                temp[s.charAt(startIndex)-'a']++;
                positiveCount++;

            }


        }


        return resultList;
    }
}

class CharContainer{
    // char的数量
    int[] charCount;
    // 推送的char的队列
    char[] charQueue;
    int index;

    public CharContainer(String p) {
        charCount=new int[26];
        for (char c : p.toCharArray()) {
            charCount[c-'a']++;
        }
        charQueue=new char[p.length()];
        index=0;
    }

    public boolean canPush(char c){
        return charCount[c-'a']==0;
    }

    public boolean isFull(){
        // 可优化
        for(int count:charCount){
            if(count>0){
                return false;
            }
        }
        return true;
    }

    public void push(char c){
        charCount[c-'a']--;
        charQueue[index++]=c;
        if (index==charQueue.length) {
            index=0;
        }
    }

    public void pop(char c){
        int popSize=0;

    }
}
